package leetcode101.data_structure;

import java.util.*;

/**
 * @author Synhard
 * @version 1.0
 * @class Code15
 * @description 332. 重新安排行程
 * 给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。
 * 所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。
 *
 *  
 *
 * 提示：
 *
 * 如果存在多种有效的行程，请你按字符自然排序返回最小的行程组合。例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前
 * 所有的机场都用三个大写字母表示（机场代码）。
 * 假定所有机票至少存在一种合理的行程。
 * 所有的机票必须都用一次 且 只能用一次。
 *  
 *
 * 示例 1：
 *
 * 输入：[["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
 * 输出：["JFK", "MUC", "LHR", "SFO", "SJC"]
 * 示例 2：
 *
 * 输入：[["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
 * 输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
 * 解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"]。但是它自然排序更大更靠后。
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-05-15 8:30
 */
public class Code15 {
    public static void main(String[] args) {
        List<List<String>> tickets = new ArrayList<>();
//        tickets.add(Arrays.asList("JFK","KUL"));
//        tickets.add(Arrays.asList("JFK","NRT"));
//        tickets.add(Arrays.asList("NRT","JFK"));
        tickets.add(Arrays.asList("JFK","SFO"));
        tickets.add(Arrays.asList("JFK","ATL"));
        tickets.add(Arrays.asList("SFO","ATL"));
        tickets.add(Arrays.asList("ATL","JFK"));
        tickets.add(Arrays.asList("ATL","SFO"));
        System.out.println(findItinerary(tickets));
    }

    private static List<String> res;

    public static List<String> findItinerary(List<List<String>> tickets) {
        res = new ArrayList<>();
        //from,             dest,    number
        Map<String, TreeMap<String, Integer>> map = new HashMap<>();
        for(List<String> ticket : tickets){
            String from = ticket.get(0);
            String to   = ticket.get(1);

            map.putIfAbsent(from, new TreeMap<>());
            TreeMap<String, Integer> treeMap = map.get(from);
            treeMap.put(to, treeMap.getOrDefault(to, 0) + 1);
        }

        res.add("JFK");
        backtrack(tickets, map, 0);

        return res;
    }

    private static boolean backtrack(List<List<String>> tickets, Map<String, TreeMap<String, Integer>> map,int progress){
        if(progress == tickets.size()){
            return true;
        }

        TreeMap<String, Integer> tos = map.get(res.get(res.size() - 1));
        if(tos == null || tos.isEmpty()) {
            return false;
        } else {
            tos.size();
        }

        for(String str : tos.keySet()){
            if(tos.get(str) == 0) {
                continue;
            }

            res.add(str);
            tos.put(str, tos.get(str) - 1);

            if(backtrack(tickets, map, progress + 1)) {
                return true;
            }

            res.remove(res.size() - 1);
            tos.put(str, tos.get(str) + 1);
        }

        return false;
    }

}

/*
对于treeMap来说如果其key值是String的话，默认是按照字典顺序排序的

HashMap<String, TreeMap<String, Integer>>
那么Key代表的是始发地， Value中的Key代表了目的地，而Value中的Value则代表了始发地到目的地的票有几张
那么首先呢我们要遍历所有的tickets将所有的ticket加入map中
这里有一点要注意就是向treeMap中的加入的Key如果是String类型的话默认是按照字典顺序进行排序的
那么我们再遍历完map之后要做的就是深度优先搜索
为什么要进行深度优先搜索呢，因为已经把所有的目的地按照字典顺序排好了，要做的就是按照顺序进行遍历，也就是深度优先搜索即可
这道题真的是太妙了
 */